/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/binary-tree-maximum-path-sum
@Language: C++
@Datetime: 16-02-09 05:43
*/

class Solution {
	struct ptrcompless{
		bool operator()(const TreeNode* ptr1,const TreeNode* ptr2)const{
			return ptr1 <ptr2;
		}
	};
    map<TreeNode*,int,ptrcompless> ms;
    int maxsum;
	int getmax(int l,int r,int val){
		vector<int> v(6);
		v[0]=l,v[1]=r,v[2]=val;
		v[3]=l+v[2],v[4]=r+v[2],v[5]=l+r+v[2];
		sort(v.begin(),v.end());
		return v[5];
	}
    int maxPathCore(TreeNode *root){
        if (root==NULL)
            return 0;
        map<TreeNode*,int,ptrcompless>::iterator it;
        it = ms.find(root);
        if (it!=ms.end())
            return it->second;
        int l=0,r=0;
        if (root->left){
            it = ms.find(root->left);
            if (it!=ms.end())
                l = it->second;
            else{
                l = maxPathCore(root->left);
                ms.insert(make_pair(root->left,l));
            }
        }
        if (root->right){
            it = ms.find(root->right);
            if (it!=ms.end())
                r = it->second;
            else{
                r = maxPathCore(root->right);
                ms.insert(make_pair(root->right,r));
            }
        }		
		l = (l>r?l:r)+root->val;
        ms.insert(make_pair(root,l));
        return l;
    }
    void preOrder(TreeNode *root){
        if (root==NULL)
            return ;
		int l= maxPathCore(root->left);
		int r = maxPathCore(root->right);
		if (root->left && root->right)
			l = getmax(l,r,root->val);
		else if (root->left){
			r = l+root->val;
			l = (l>root->val?l:root->val);
			l = (l>r?l:r);
		}
		else if (root->right){			
			l = (r>root->val?r:root->val);
			r = r+root->val;
			l = (l>r?l:r);
		}
		else
			l = root->val;
        maxsum = (maxsum>l?maxsum:l);
        preOrder(root->left);
        preOrder(root->right);
    }
public:
    
    int maxPathSum(TreeNode *root) {
        // write your code here
        maxsum = -(1<<30);
        ms.clear();
        preOrder(root);
        return maxsum;
    }
};